﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Algorithm.Struct;

namespace Algorithm.SortAlgorithm
{
    public static class HuffMan
    {
        public static BTree<code> HuffManCoding(code[] co)
        {
            var nodes = Array.ConvertAll(co, (c) => { return new TreeNode<code>(c); });

            MinHeapSort<TreeNode<code>> minHeap = new MinHeapSort<TreeNode<code>>(nodes);
            var len = co.Length;

            for (int i = 0; i < len-1; i++)
            {
                var c = new code();
                TreeNode<code> codeNode = new TreeNode<code>(c);
                codeNode.LeftNode = minHeap.MinHeap_Extract_Min();
                codeNode.RightNode = minHeap.MinHeap_Extract_Min();
                c.f = codeNode.LeftNode.Data.f + codeNode.RightNode.Data.f;
                minHeap.MinHeap_Insert(codeNode,new TreeNode<code>(new code(){f= int.MaxValue}));
            }

            var root = minHeap.MinHeap_Minimum();
            return new BTree<code>(root);
        }        
    }

    public class code:IComparable<code>
    {
        public char c;
        public int f;

        public int CompareTo(code other)
        {
            return f.CompareTo(other.f);
        }
    }
}
